//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 
//
// 你的算法时间复杂度必须是 O(log n) 级别。 
//
// 如果数组中不存在目标值，返回 [-1, -1]。 
//
// 示例 1: 
//
// 输入: nums = [5,7,7,8,8,10], target = 8
//输出: [3,4] 
//
// 示例 2: 
//
// 输入: nums = [5,7,7,8,8,10], target = 6
//输出: [-1,-1] 
// Related Topics 数组 二分查找 
// 👍 616 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：在排序数组中查找元素的第一个和最后一个位置
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P34_FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new P34_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        // TODO 此处开始你的表演
        solution.searchRange(MyUtil.createArray(5, 7, 7, 8, 8, 8, 9, 10), 6);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int left = searchLeft(nums, target, true);
            int right = searchLeft(nums, target, false);
            return new int[]{left, right};
        }

        private int searchLeft(int[] nums, int target, boolean leftFlag) {
            if (nums == null) {
                return -1;
            }
            int left = 0, right = nums.length - 1, result = -1;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (nums[mid] == target) {
                    result = mid;
                    if (leftFlag) {
                        // 取最小值
                        right = mid - 1;
                    } else {
                        // 取最大值
                        left = mid + 1;
                    }
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                }
            }

            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}